package homework04;

public class HeapManager1 {
    static private final int NULL = -1;
	private int[] memory;
	private int freeStart;
    
    
	public HeapManager1(int[] initialMemory){
		memory = initialMemory;
		memory[0] = memory.length;
		memory[1] = NULL; 
	}
	
	
	public int allocate(int requestSize){
		int size = requestSize + 1;
		
		
		/*Do best-fit search: check all blocks to find the best-fit
		 * Stop if a block is the perfect size.
		 */
		int p = freeStart;
		int lag = NULL;
		int bestBlock = NULL;
		int bestLag = NULL;
		
		/*Find the best-fit block to add to*/
		while(p != NULL){
			int s = memory[p] - size;   //difference between a free block and space needed for allocation
			
			if(s >= 0){				
				if(bestBlock == NULL || s < (memory[bestBlock] - size)){		//first block that is big enough
					bestLag = lag;												//or next smaller block
					bestBlock = p;
				}	
			}
			
			lag = p;
			p = memory[p+1];
									
		}//end while
		
		/*Now we have
		 * 
		 * bestLag = free block before the block that is the best fit,  or null
		 * bestBlock = the block that is the best-fit for allocation,   or null
		 * 
		 */
		
		
		if(bestBlock == NULL)
			throw new OutOfMemoryError();
		int nextFree = memory[bestBlock+1];
		
		
		//If the block has more space than we need, carve out what we need from the front
		//and return the unused end part to the free list
		
		int unused = memory[bestBlock] - size; //extra space in block

			
		if(unused >= 1){
			if(bestLag != NULL && (bestLag + memory[bestLag] == bestBlock) ){ //block below is free
				memory[bestLag] += unused;
				memory[bestLag + 1] = memory[bestBlock + 1];
				memory[bestBlock] = 0;
				memory[bestBlock + 1] = 0;
				memory[bestBlock + unused] = size;
				memory[bestBlock + unused + 1] = NULL;
			}else if((memory[bestBlock] + bestBlock + 1 < memory.length) && (memory[memory[bestBlock] + bestBlock + 1]) != NULL){  //block above is free
				int nxtBlock = bestBlock + memory[bestBlock];
				
				//merge the top block with the unused portion of the lower block
				nextFree = bestBlock + size;
			
				memory[bestBlock + size] = unused + memory[nxtBlock];
				if(memory[nxtBlock + 1] != bestBlock)
					memory[bestBlock + size + 1] = memory[nxtBlock+ 1];
				else
					memory[bestBlock + size + 1] = memory[bestBlock + 1];
				memory[nxtBlock] = 0;
				memory[nxtBlock + 1] = 0;
				
				//set the lower, used, blocks values
				memory[bestBlock] = size;
				memory[bestBlock + 1] = NULL;

				bestLag = NULL;
			}else if(bestLag == NULL){
				nextFree = bestBlock + size; //index of the unused piece
				memory[nextFree] = unused; //fill in the size
				memory[nextFree + 1] = memory[bestBlock+1]; //fill in link
				memory[bestBlock] = size; //reduce p's size accordingly
			}else{
				nextFree = bestBlock + size; 
				memory[nextFree] = unused;
				memory[nextFree + 1] = memory[bestBlock+1];
				memory[bestBlock] = size;
				
			}
		}else{// if(unused == 0){
			nextFree = memory[bestBlock +1];
			memory[bestBlock +1] = NULL;
		}
		
		
		
		//Link out the block we are allocating and done.
		if(bestLag == NULL) freeStart = nextFree;
		else memory[bestLag+1] = nextFree;
		return bestBlock+1; //index of useable word (after header)		
		
	}//end allocate
	
	
	public void deallocate(int address){
		int addr = address-1;
		memory[addr + 1] = freeStart;
		freeStart = addr;
	}
	
	public int getFreeStart(){
		return freeStart;
	}
	
	public void defrag(){
		
	}
	
	
	
   //test edit from google code site
	
}
